home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Internet Tools 1995 April / Internet Tools.iso / ip / ppp / mac / macppp2.0.1-src.hqx / MacPPP 2.0.1 src / slhc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-10-08  |  13.5 KB  |  506 lines
  1. /*
  2.  * Routines to compress and uncompress tcp packets (for transmission
  3.  * over low speed serial lines.
  4.  *
  5.  * Copyright (c) 1989 Regents of the University of California.
  6.  * All rights reserved.
  7.  *
  8.  * Redistribution and use in source and binary forms are permitted
  9.  * provided that the above copyright notice and this paragraph are
  10.  * duplicated in all such forms and that any documentation,
  11.  * advertising materials, and other materials related to such
  12.  * distribution and use acknowledge that the software was developed
  13.  * by the University of California, Berkeley.  The name of the
  14.  * University may not be used to endorse or promote products derived
  15.  * from this software without specific prior written permission.
  16.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  17.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  18.  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  19.  *
  20.  *    Van Jacobson (van@helios.ee.lbl.gov), Dec 31, 1989:
  21.  *    - Initial distribution.
  22.  *
  23.  * modified for KA9Q Internet Software Package by
  24.  * Katie Stevens (dkstevens@ucdavis.edu)
  25.  * University of California, Davis
  26.  * Computing Services
  27.  *    - 01-31-90    initial adaptation (from 1.19)
  28.  *    PPP.05    02-15-90 [ks]
  29.  *    PPP.08    05-02-90 [ks]    use PPP protocol field to signal compression
  30.  *    PPP.15    09-90     [ks]    improve mbuf handling
  31.  *    PPP.16    11-02     [karn]    substantially rewritten to use NOS facilities
  32.  *
  33.  *    - Feb 1991    Bill_Simpson@um.cc.umich.edu
  34.  *            variable number of conversation slots
  35.  *            allow zero or one slots
  36.  *            separate routines
  37.  *            status display
  38.  *
  39.  *  1992-93  Modifications for MacPPP.
  40.  *                -Larry Blunk, Merit Network, Inc./ University of Michigan
  41.  */
  42.  
  43. #include "ppp.h"
  44. #include "slhc.h"
  45.  
  46. /* Initialize compression data structure
  47.  *    slots must be in range 0 to 255 (zero meaning no compression)
  48.  */
  49. void
  50. slhc_init( LapInfo *lap, short rslots, short tslots )
  51. {
  52.     b_16 i;
  53.     struct cstate *ts;
  54.  
  55.     if ( rslots > 0  &&  rslots <= MAXSLOTS ) {
  56.         lap->comp.rstate = lap->rcvslots;
  57.         lap->comp.rslot_limit = rslots - 1;
  58.     }
  59.  
  60.     if ( tslots > 0  &&  tslots <= MAXSLOTS ) {
  61.         lap->comp.tstate = lap->txslots;
  62.         lap->comp.tslot_limit = tslots - 1;
  63.     }
  64.  
  65.     lap->comp.xmit_oldest = 0;
  66.     lap->comp.xmit_current = lap->comp.recv_current = 255;
  67.  
  68.     if ( tslots > 0 ) {
  69.         ts = lap->comp.tstate;
  70.         for(i = lap->comp.tslot_limit; i > 0; --i){
  71.             ts[i].this = i;
  72.             ts[i].next = &(ts[i - 1]);
  73.         }
  74.         ts[0].next = &(ts[lap->comp.tslot_limit]);
  75.         ts[0].this = 0;
  76.     }
  77. }
  78.  
  79. /* Encode a number */
  80. static b_8 *
  81. encode(b_8 *cp, b_16 n)
  82. {
  83.     if(n >= 256 || n == 0){
  84.         *cp++ = 0;
  85.         *cp++ = n >> 8;
  86.     }
  87.     *cp++ = n;
  88.     return cp;
  89. }
  90.  
  91. /* Decode a number */
  92. static long
  93. decode(struct bufheader *bufptr)
  94. {
  95.     short x;
  96.  
  97.     x = yankbyte(bufptr);
  98.     if (x == 0) {
  99.         return yank16(bufptr);    /* yank16 returns -1 on error */
  100.     } else {
  101.         return (long)x;        /* -1 if error */
  102.     }
  103. }
  104.  
  105. short
  106. slhc_compress(LapInfo *lap, struct bufheader *bufptr, short compress_cid)
  107. {
  108.     struct slcompress *comp = &(lap->comp);
  109.     struct cstate *ocs = &(comp->tstate[comp->xmit_oldest]);
  110.     struct cstate *lcs = ocs;
  111.     struct cstate *cs = lcs->next;
  112.     b_16 hiplen, htcplen, hlen;
  113.     b_16 ipoptlen, tcpoptlen;
  114.     struct tcpheader *oth;
  115.     unsigned long deltaS, deltaA;
  116.     b_16 changes = 0;
  117.     b_8 new_seq[16];
  118.     b_8 *cp = new_seq;
  119.     struct tcpheader th;
  120.     struct ipheader iph;
  121.  
  122.     /* Extract IP header */
  123.     hiplen = getipheader(&iph,bufptr);
  124.     /* Bail if this packet isn't TCP, or is an IP fragment */
  125.     if(iph.protocol != TCP_PROTOCOL || (iph.offset & 0x3fff) != 0 ){
  126.         bufptr->dataptr -= hiplen;
  127.         bufptr->length += hiplen;
  128.         return SL_TYPE_IP;
  129.     }
  130.     /* Extract TCP header */
  131.     htcplen = gettcpheader(&th,bufptr);
  132.     hlen = hiplen + htcplen;
  133.  
  134.     /*  Bail if the TCP packet isn't `compressible' (i.e., ACK isn't set or
  135.      *  some other control bit is set).
  136.      */
  137.     if((th.flags & ( TCP_FIN | TCP_SYN | TCP_ACK | TCP_RST )) ^ TCP_ACK ){
  138.         /* TCP connection stuff; send as regular IP */
  139.         bufptr->dataptr -= hlen;
  140.         bufptr->length += hlen;
  141.         return SL_TYPE_IP;
  142.     }
  143.     /*
  144.      * Packet is compressible -- we're going to send either a
  145.      * COMPRESSED_TCP or UNCOMPRESSED_TCP packet.  Either way,
  146.      * we need to locate (or create) the connection state.
  147.      *
  148.      * States are kept in a circularly linked list with
  149.      * xmit_oldest pointing to the end of the list.  The
  150.      * list is kept in lru order by moving a state to the
  151.      * head of the list whenever it is referenced.  Since
  152.      * the list is short and, empirically, the connection
  153.      * we want is almost always near the front, we locate
  154.      * states via linear search.  If we don't find a state
  155.      * for the datagram, the oldest state is (re-)used.
  156.      */
  157.     for ( ; ; ) {
  158.         if( iph.source_addr == cs->cs_ip.source_addr
  159.          && iph.dest_addr == cs->cs_ip.dest_addr
  160.          && th.source_port == cs->cs_tcp.source_port
  161.          && th.dest_port == cs->cs_tcp.dest_port)
  162.             goto found;
  163.  
  164.         /* if current equal oldest, at end of list */
  165.         if ( cs == ocs )
  166.             break;
  167.         lcs = cs;
  168.         cs = cs->next;
  169.     };
  170.     /*
  171.      * Didn't find it -- re-use oldest cstate.  Send an
  172.      * uncompressed packet that tells the other side what
  173.      * connection number we're using for this conversation.
  174.      *
  175.      * Note that since the state list is circular, the oldest
  176.      * state points to the newest and we only need to set
  177.      * xmit_oldest to update the lru linkage.
  178.      */
  179.     comp->xmit_oldest = lcs->this;
  180.  
  181.     goto uncompressed;
  182.  
  183. found:
  184.     /*
  185.      * Found it -- move to the front on the connection list.
  186.      */
  187.     if(lcs == ocs) {
  188.         /* found at most recently used */
  189.     } else if (cs == ocs) {
  190.         /* found at least recently used */
  191.         comp->xmit_oldest = lcs->this;
  192.     } else {
  193.         /* more than 2 elements */
  194.         lcs->next = cs->next;
  195.         cs->next = ocs->next;
  196.         ocs->next = cs;
  197.     }
  198.  
  199.     /*
  200.      * Make sure that only what we expect to change changed.
  201.      * Check the following:
  202.      * IP protocol version, header length & type of service.
  203.      * The "Don't fragment" bit.
  204.      * The time-to-live field.
  205.      * The TCP header length.
  206.      * IP options, if any.
  207.      * TCP options, if any.
  208.      * If any of these things are different between the previous &
  209.      * current datagram, we send the current datagram `uncompressed'.
  210.      */
  211.     oth = &cs->cs_tcp;
  212.  
  213.     ipoptlen = hiplen - IPHLEN;
  214.     tcpoptlen = htcplen - TCPHLEN;
  215.     if (iph.version != cs->cs_ip.version
  216.      || iph.tos != cs->cs_ip.tos
  217.      || (iph.offset ^ cs->cs_ip.offset) & IP_DONT_FRAG
  218.      || iph.ttl != cs->cs_ip.ttl
  219.      || (th.offset ^ cs->cs_tcp.offset) & 0xf0
  220.      || (ipoptlen > 0 && bytecmp(iph.options,cs->cs_ip.options,
  221.                          ipoptlen) != 0)
  222.      || (tcpoptlen > 0 && bytecmp(th.options,cs->cs_tcp.options,
  223.                  tcpoptlen) != 0)){
  224.         goto uncompressed;
  225.     }
  226.     /*
  227.      * Figure out which of the changing fields changed.  The
  228.      * receiver expects changes in the order: urgent, window,
  229.      * ack, seq (the order minimizes the number of temporaries
  230.      * needed in this section of code).
  231.      */
  232.     if(th.flags & TCP_URG){
  233.         deltaS = th.urgent_pointer;
  234.         cp = encode(cp,deltaS);
  235.         changes |= NEW_U;
  236.     } else if (th.urgent_pointer != oth->urgent_pointer){
  237.         /* argh! URG not set but urp changed -- a sensible
  238.          * implementation should never do this but RFC793
  239.          * doesn't prohibit the change so we have to deal
  240.          * with it. */
  241.         goto uncompressed;
  242.     }
  243.     if((deltaS = th.window - oth->window) != 0){
  244.         cp = encode(cp,deltaS);
  245.         changes |= NEW_W;
  246.     }
  247.     if((deltaA = th.acknowledge - oth->acknowledge) != 0L){
  248.         if(deltaA > 0x0000ffff)
  249.             goto uncompressed;
  250.         cp = encode(cp,deltaA);
  251.         changes |= NEW_A;
  252.     }
  253.     if((deltaS = th.sequence - oth->sequence) != 0L){
  254.         if(deltaS > 0x0000ffff)
  255.             goto uncompressed;
  256.         cp = encode(cp,deltaS);
  257.         changes |= NEW_S;
  258.     }
  259.  
  260.     switch(changes){
  261.     case 0:    /* Nothing changed. If this packet contains data and the
  262.          * last one didn't, this is probably a data packet following
  263.          * an ack (normal on an interactive connection) and we send
  264.          * it compressed.  Otherwise it's probably a retransmit,
  265.          * retransmitted ack or window probe.  Send it uncompressed
  266.          * in case the other side missed the compressed version.
  267.          */
  268.         if(iph.length != cs->cs_ip.length && cs->cs_ip.length == hlen)
  269.             break;
  270.         goto uncompressed;
  271.     case SPECIAL_I:
  272.     case SPECIAL_D:
  273.         /* actual changes match one of our special case encodings --
  274.          * send packet uncompressed.
  275.          */
  276.         goto uncompressed;
  277.     case NEW_S|NEW_A:
  278.         if(deltaS == deltaA &&
  279.             deltaS == cs->cs_ip.length - hlen){
  280.             /* special case for echoed terminal traffic */
  281.             changes = SPECIAL_I;
  282.             cp = new_seq;
  283.         }
  284.         break;
  285.     case NEW_S:
  286.         if(deltaS == cs->cs_ip.length - hlen){
  287.             /* special case for data xfer */
  288.             changes = SPECIAL_D;
  289.             cp = new_seq;
  290.         }
  291.         break;
  292.     }
  293.     deltaS = iph.id - cs->cs_ip.id;
  294.     if(deltaS != 1){
  295.         cp = encode(cp,deltaS);
  296.         changes |= NEW_I;
  297.     }
  298.     if(th.flags & TCP_PUSH)
  299.         changes |= TCP_PUSH_BIT;
  300.     /* Grab the cksum before we overwrite it below.  Then update our
  301.      * state with this packet's header.
  302.      */
  303.     deltaA = th.checksum;
  304.  
  305.     BlockMove(&iph, &cs->cs_ip, hiplen);
  306.     BlockMove(&th, &cs->cs_tcp, htcplen);
  307.  
  308.     /* We want to use the original packet as our compressed packet.
  309.      * (cp - new_seq) is the number of bytes we need for compressed
  310.      * sequence numbers.  In addition we need one byte for the change
  311.      * mask, one for the connection id and two for the tcp checksum.
  312.      * So, (cp - new_seq) + 4 bytes of header are needed.
  313.      */
  314.     deltaS = cp - new_seq;
  315.     if(compress_cid == 0 || comp->xmit_current != cs->this){
  316.         makeroom(bufptr, deltaS + 4);
  317.         cp = bufptr->dataptr;
  318.         *cp++ = changes | NEW_C;
  319.         *cp++ = cs->this;
  320.         comp->xmit_current = cs->this;
  321.     } else {
  322.         makeroom(bufptr,deltaS + 3);
  323.         cp = bufptr->dataptr;
  324.         *cp++ = changes;
  325.     }
  326.     *cp++ = deltaA >> 8;    /* Write TCP checksum */
  327.     *cp++ = deltaA;
  328.     BlockMove(new_seq,cp,(long)deltaS);    /* Write list of deltas */
  329.     return SL_TYPE_COMPRESSED_TCP;
  330.  
  331.     /* Update connection state cs & send uncompressed packet (i.e.,
  332.      * a regular ip/tcp packet but with the 'conversation id' we hope
  333.      * to use on future compressed packets in the protocol field).
  334.      */
  335. uncompressed:
  336.     iph.protocol = cs->this;
  337.     BlockMove(&iph, &cs->cs_ip, hiplen);
  338.     BlockMove(&th, &cs->cs_tcp, htcplen);
  339.     comp->xmit_current = cs->this;
  340.     bufptr->dataptr -= hlen;
  341.     bufptr->length += hlen;
  342.     *(bufptr->dataptr + IP_PROTO_OFFSET) = iph.protocol;
  343.     return SL_TYPE_UNCOMPRESSED_TCP;
  344. }
  345.  
  346. short
  347. slhc_uncompress(LapInfo *lap, struct bufheader *bufptr)
  348. {
  349.     struct slcompress *comp = &(lap->comp);
  350.     short changes;
  351.     long x;
  352.     unsigned long cksum;
  353.     b_16 *ptr;
  354.     unsigned short ipheadlen;
  355.     unsigned short sumword;
  356.     struct tcpheader *thp;
  357.     struct cstate *cs;
  358.     short len;
  359.  
  360.     /* We've got a compressed packet; read the change byte */
  361.     if (bufptr->length < 3)
  362.         return 0;
  363.         
  364.     changes = yankbyte(bufptr);    /* "Can't fail" */
  365.     if(changes & NEW_C){
  366.         /* Make sure the state index is in range, then grab the state.
  367.          * If we have a good state index, clear the 'discard' flag.
  368.          */
  369.         x = yankbyte(bufptr);    /* Read conn index */
  370.         if(x < 0 || x > comp->rslot_limit)
  371.             goto bad;
  372.  
  373.         comp->flags &=~ SLF_TOSS;
  374.         comp->recv_current = x;
  375.     } else {
  376.         /* this packet has an implicit state index.  If we've
  377.          * had a line error since the last time we got an
  378.          * explicit state index, we have to toss the packet. */
  379.         if(comp->flags & SLF_TOSS)
  380.             return 0;
  381.     }
  382.     cs = &comp->rstate[comp->recv_current];
  383.     thp = &cs->cs_tcp;
  384.     
  385.     ipheadlen = (cs->cs_ip.version & 0x0f) << 2 ;
  386.  
  387.     if((x = yank16(bufptr)) == -1)    /* Read the TCP checksum */
  388.         goto bad;
  389.     thp->checksum = x;
  390.  
  391.     if (changes & TCP_PUSH_BIT)
  392.         thp->flags |= TCP_PUSH;
  393.     else
  394.         thp->flags &= ~TCP_PUSH;
  395.  
  396.     switch(changes & SPECIALS_MASK){
  397.     case SPECIAL_I:        /* Echoed terminal traffic */
  398.         {
  399.         b_16 i;
  400.         i = cs->cs_ip.length;
  401.         i -= ( ipheadlen + TCPHLEN);
  402.         thp->acknowledge += i;
  403.         thp->sequence += i;
  404.         }
  405.         break;
  406.  
  407.     case SPECIAL_D:            /* Unidirectional data */
  408.         thp->sequence += cs->cs_ip.length - (ipheadlen + TCPHLEN);
  409.         break;
  410.  
  411.     default:
  412.         if(changes & NEW_U){
  413.             thp->flags |= TCP_URG;
  414.             if((x = decode(bufptr)) == -1)
  415.                 goto bad;
  416.             thp->urgent_pointer = x;
  417.         } else
  418.             thp->flags &= ~TCP_URG;
  419.         if(changes & NEW_W){
  420.             if((x = decode(bufptr)) == -1)
  421.                 goto bad;
  422.             thp->window += x;
  423.         }
  424.         if(changes & NEW_A){
  425.             if((x = decode(bufptr)) == -1)
  426.                 goto bad;
  427.             thp->acknowledge += x;
  428.         }
  429.         if(changes & NEW_S){
  430.             if((x = decode(bufptr)) == -1)
  431.                 goto bad;
  432.             thp->sequence += x;
  433.         }
  434.         break;
  435.     }
  436.     if(changes & NEW_I){
  437.         if((x = decode(bufptr)) == -1)
  438.             goto bad;
  439.         cs->cs_ip.id += x;
  440.     } else
  441.         cs->cs_ip.id++;
  442.  
  443.     /*
  444.      * At this point, the buffer points to the first byte of data in the
  445.      * packet.  Put the reconstructed TCP and IP headers back on the
  446.      * packet.  Recalculate IP checksum (but not TCP checksum).
  447.      */
  448.     len =  bufptr->length + ipheadlen + TCPHLEN;
  449.     cs->cs_ip.length = len;
  450.  
  451.     puttcpheader(thp,bufptr);
  452.     
  453.     /* need to recalc IP header checksum here */
  454.     cs->cs_ip.checksum = 0;
  455.     ipheadlen >>= 1;
  456.     ptr = (b_16 *) &cs->cs_ip;
  457.     cksum = 0;
  458.     while (ipheadlen-- != 0)
  459.         cksum += *ptr++;
  460.     while ((sumword = cksum >> 16) != 0)
  461.         cksum = sumword + (cksum & 0xffffL);
  462.     cs->cs_ip.checksum = ~cksum & 0xffffL;
  463.     putipheader(&cs->cs_ip,bufptr);
  464.     return len;
  465. bad:
  466.     return slhc_toss( comp );
  467. }
  468.  
  469. short
  470. slhc_remember(LapInfo *lap, struct bufheader *bufptr)
  471. {
  472.     struct slcompress *comp = &lap->comp;
  473.     struct cstate *cs;
  474.     struct ipheader iph;
  475.     struct tcpheader th;
  476.     register unsigned short headerlen;
  477.     b_8 slot_id;
  478.     
  479.     /*  verify slot ID */
  480.     if( (slot_id = *(bufptr->dataptr + IP_PROTO_OFFSET)) > comp->rslot_limit) {
  481.         PPP_DEBUG_CHECKS("\pillegal slot num");
  482.         return slhc_toss(comp);
  483.     }
  484.  
  485.     /* Update local state */
  486.     cs = &comp->rstate[comp->recv_current = slot_id];
  487.     comp->flags &=~ SLF_TOSS;
  488.     *(bufptr->dataptr + IP_PROTO_OFFSET) = TCP_PROTOCOL; /* restore proto */
  489.  
  490.     headerlen = getipheader(&cs->cs_ip,bufptr);
  491.     headerlen += gettcpheader(&cs->cs_tcp,bufptr);
  492.  
  493.     /* Put headers back on packet */
  494.     bufptr->dataptr -= headerlen;
  495.     bufptr->length += headerlen;
  496.  
  497.     return (bufptr->length);
  498. }
  499.  
  500. short
  501. slhc_toss(struct slcompress *comp)
  502. {
  503.     comp->flags |= SLF_TOSS;
  504.     return 0;
  505. }
  506.